package tuopu;

import pojo.EdgeWithoutVal;

import java.util.*;

/**
 * <p>
 *     拓扑排序，个人理解就是讲先后顺序，同学们可以类比如，
 *     你要先学会一门编程语言才能刷算法题，你要先脱衣服才能洗澡（总不能有人穿衣服洗澡吧~）
 *     那么在这些例子中，其中的先做...后做...就形成了一种拓扑序
 *     拓扑序的实现常用有两种，这里展示大家数据结构课里需要学习的kahn算法实现
 * </p>
 * @author 没天赋
 * @since 2025-3-1
 */
@SuppressWarnings(value = "all")
public class tuopu {
    //定义最大点数
    public static final int N = (int) (1e5 + 5);
    //定义边数组,这里*2是因为无向图
    public static EdgeWithoutVal[] edges = new EdgeWithoutVal[N << 1];
    //存邻接表头
    public static int[] head = new int[N];
    //保存拓扑序
    public static ArrayList<Integer> topo = new ArrayList<>();
    //kahn算法的关键，就是利用queue实现bfs
    public static Queue<Integer> queue = new LinkedList<>();
    //记录是否访问
    public static int[] vis = new int[N];
    //记录入度数量
    public static int[] in = new int[N];
    //点数n，边数m,下标id（记录边数）,入度u，出度v，记录进入拓扑序的点数
    public static int n, m, id, u, v,num;
    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        n = sin();
        m = sin();
        for (int i = 0; i < m; i++) {
            u = sin();
            v = sin();
            add(u,v);
        }
        //开始kahn算法
        if (kahn()) {
            //如果其中无环，输出拓扑序
            topo.forEach(System.out::println);
        } else {
            //如果有环，输出有环
            System.out.println("有环");
        }
    }

    public static boolean kahn() {
        //遍历入度，如果入度为0，则入队列
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            //出队列，并记录进入拓扑序的点数
            Integer temp = queue.poll();
            topo.add(temp);
            num++;
            //遍历临边，临边入度-1
            for (int i = head[temp]; i != 0; i = edges[i].next) {
                int x = edges[i].to;
                in[x]--;
                //如果入度为0，则入队列
                if (in[x] == 0) {
                    queue.add(x);
                }
            }
        }
        //如果进入拓扑序的点数等于点数，则无环，否则有环（这里不理解的同学可以动手画一画，画出来就不难理解啦）
        return num == n;
    }

    /**
     * 增边
     *
     * @param x
     * @param y
     * @param z
     */
    public static void add(int x, int y) {
        id++;
        edges[id] = new EdgeWithoutVal(y, head[x]);
        in[y]++;
        head[x] = id;
    }

    /**
     * 读取整数方法
     *
     * @return
     */
    public static int sin() {
        return sc.nextInt();
    }
}

/**
 * 测试数据：
 * 数据1（正常情况）
 * 5 5
 * 1 2
 * 2 4
 * 3 2
 * 3 4
 * 4 5
 * ---------
 * 1 3 2 4 5
 *
 *数据2（有环）
 * 4 4
 * 4 1
 * 1 2
 * 2 3
 * 3 1
 * ----------
 * 有环
 */